2017 Kakao Qualifying

Coloring book (Lv. 2)
https://school.programmers.co.kr/learn/courses/30/lessons/1829
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void propa(vector<vector<int>>& picture, int& size, int value, int i, int j){
if(j!=0 && picture[i][j-1]==value){
picture[i][j-1]=0;
size++;
propa(picture, size, value, i, j-1);
}
if(i!=0 && picture[i-1][j]==value){
picture[i-1][j]=0;
size++;
propa(picture, size, value, i-1, j);
}
if(j!=picture[0].size()-1 && picture[i][j+1]==value){
picture[i][j+1]=0;
size++;
propa(picture, size, value, i, j+1);
}
if(i!=picture.size()-1 && picture[i+1][j]==value){
picture[i+1][j]=0;
size++;
propa(picture, size, value, i+1, j);
}
return;
}
vector<int> solution(int m, int n, vector<vector<int>> picture){
int number_of_area=0;
int max_size_of_one_area=0;
int size, value;
for(int i=0; i<m; ++i){
for(int j=0; j<n; ++j){
if(picture[i][j]!=0){
size=0;
value=picture[i][j];
propa(picture, size, value, i, j);
if(max_size_of_one_area<size) max_size_of_one_area=size;
number_of_area++;
}
}
}
vector<int> answer(2);
answer[0]=number_of_area;
answer[1]=max_size_of_one_area;
return answer;
}
int main(void){
int m, n;
vector<vector<int>> picture={
{1, 1, 1, 0},
{1, 2, 2, 0},
{1, 0, 0, 1},
{0, 0, 0, 1},
{0, 0, 0, 3},
{0, 0, 0, 3}
};
m=picture.size();
n=picture[0].size();
vector<int> result=solution(m, n, picture);
cout<<"Result: \n";
cout<<"["<<result[0]<<", "<<result[1]<<"]";
}
Pedestrian world (Lv. 3)
https://school.programmers.co.kr/learn/courses/30/lessons/1832
#include <iostream>
#include <vector>
using namespace std;
int MOD=20170805;
void state(int i, int j, vector<vector<int>> city_map, int& count, int dir){
if(i==city_map.size()-1 && j==city_map[0].size()-1){
count++;
count%=MOD;
return;
}
if(i==city_map.size() || j==city_map[0].size()){
return;
}
if(city_map[i][j]==0){
state(i+1, j, city_map, count, 0);
state(i, j+1, city_map, count, 1);
} else if(city_map[i][j]==1){
return;
} else{
if(dir) state(i, j+1, city_map, count, dir);
else state(i+1, j, city_map, count, dir);
}
}
int solution(int m, int n, vector<vector<int>> city_map){
int answer=0;
int count=0;
state(0, 0, city_map, count, 3);
answer=count;
return answer;
}
int main(void){
int m, n, answer;
vector<vector<int>> city_map={
{0, 2, 0, 0, 0, 2},
{0, 0, 2, 0, 1, 0},
{1, 0, 0, 2, 2, 0}
};
m=city_map.size(); n=city_map[0].size();
answer=solution(m, n, city_map);
cout<<"answer: "<<answer<<endl;
return 0;
}
Camping (Lv. 3)
https://school.programmers.co.kr/learn/courses/30/lessons/1833
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int n, vector<vector<int>> data){
int answer=0, state;
int xmin, xmax, ymin, ymax;
for(int i=0; i<n; ++i){
for(int j=i+1; j<n; ++j){
if(data[i][0]==data[j][0] || data[i][1]==data[j][1]) continue;
xmin=min(data[i][0], data[j][0]); xmax=max(data[i][0], data[j][0]);
ymin=min(data[i][1], data[j][1]); ymax=max(data[i][1], data[j][1]);
state=0;
for(int l=0; l<n; ++l){
if(data[l][0]>xmin && data[l][0]<xmax && data[l][1]>ymin && data[l][1]<ymax) break;
state++;
}
if(state==n) answer++;
}
}
return answer;
}
int main(void){
int n, answer;
n=4;
vector<vector<int>> data={
{0, 0},
{1, 1},
{0, 2},
{2, 0}
};
answer=solution(n, data);
cout<<"answer: "<<answer<<endl;
return 0;
}
Brian Consderation (Lv.3)
https://school.programmers.co.kr/learn/courses/30/lessons/1830
#include <iostream>
#include <string>
using namespace std;
string remove_pattern1(string sentence, char c, int start, int end){
string result;
for(int i=0; i<start-1; ++i){
result=result+sentence[i];
}
if(start!=1 && sentence[start-2]!=' ') result+=' ';
for(int i=start-1; i<=end+1; i+=2){
result=result+sentence[i];
}
if(end+2!=sentence.length()) result+=' ';
for(int i=end+2; i<sentence.length(); ++i){
result=result+sentence[i];
}
return result;
}
string remove_pattern2(string sentence, char c, int start, int end){
string result;
for(int i=0; i<start; ++i){
result=result+sentence[i];
}
if(start!=0 && sentence[start-1]!=' ') result+=' ';
for(int i=start+1; i<end; ++i){
result=result+sentence[i];
}
if(end!=sentence.length()-1) result+=' ';
for(int i=end+1; i<sentence.length(); ++i){
result=result+sentence[i];
}
return result;
}
string solution(string sentence){
int size=sentence.length();
char c;
int rep, loc;
for(int i=0; i<size; ++i){
if(islower(sentence[i]))
c=sentence[i];
rep=0;
for(int j=i+1; j<size; ++j){
if(islower(sentence[j]) && sentence[j]==c){
rep++;
loc=j;
}
}
if(rep==1){
sentence=remove_pattern2(sentence, c, i, loc);
}else if(rep>1){
if(i==0 || sentence[i-1]==' '){
sentence="invalid";
return sentence;
}
sentence=remove_pattern1(sentence, c, i, loc);
}
}
return sentence;
}
int main(void){
string sentence1="HaEaLaLaObWORLDb";
string sentence2="SpIpGpOpNpGJqOqA";
string sentence3="AxAxAxAoBoBoB";
string answer1=solution(sentence1);
string answer2=solution(sentence2);
string answer3=solution(sentence3);
cout<<"Answer1: "<<answer1<<'\n';
cout<<"Answer2: "<<answer2<<'\n';
cout<<"Answer3: "<<answer3<<endl;
return 0;
}
The High-Pitched of IU (Lv. 4)
https://school.programmers.co.kr/learn/courses/30/lessons/1831
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
void repeat(int n, int lv1, int lv2, int& answer){
if(n==1 && 2*lv1==lv2) {
answer++;
return;
}
if(2*lv1>lv2) {
return;
}
int req_lv1=lv2/2+lv2%2-lv1;
if(n<pow(3, req_lv1)) return;
if(n%3!=0){
repeat(n-1, lv1, lv2+1, answer);
}if (n%3==0){
repeat(n/3, lv1+1, lv2, answer);
repeat(n-1, lv1, lv2+1, answer);
}
}
int solution(int n){
int answer=0;
repeat(n ,0, 0, answer);
return answer;
}
int main(void){
int n=2147483647;
int result=solution(n);
std::cout<<"answer: "<<result<<std::endl;
return 0;
}
Mystery Expeditor (Lv.5)
https://school.programmers.co.kr/learn/courses/30/lessons/1834
not Solved yet
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int route(vector<vector<int>> g1, int now1, int prev1, vector<vector<int>> g2, int now2, int prev2){
vector<int> v1, v2;
for(int i=0; i<g1.size(); ++i){
if(g1[i][0]==now1 && g1[i][1]!=prev1) v1.push_back(g1[i][1]);
else if(g1[i][1]==now1 && g1[i][0]!=prev1) v1.push_back(g1[i][0]);
}
for(int i=0; i<g2.size(); ++i){
if(g2[i][0]==now2 && g2[i][1]!=prev2) v2.push_back(g2[i][1]);
else if(g2[i][1]==now2 && g2[i][0]!=prev2) v2.push_back(g2[i][0]);
}
}
int solution(int n1, vector<vector<int>> g1, int n2, vector<vector<int>> g2){
int answer=0;
route(g1, 1, 0, g2, 1, 0, 1, answer);
return answer;
}
int main(void){
int n1, n2;
n1=8; n2=9;
vector<vector<int>> g1={
{3, 1},
{5, 7},
{8, 7},
{2, 3},
{3, 6},
{1, 5},
{4, 3}
};
vector<vector<int>> g2={
{1, 5},
{5, 6},
{3, 7},
{3, 1},
{7, 4},
{7, 2},
{9, 8},
{5, 9}
};
int result=solution(n1, g1, n2, g2);
std::cout<<"Result: "<<result<<std::endl;
return 0;
}